package summer.graph;

import java.util.*;

public class Solution841 {
//    public boolean canVisitAllRooms1(List<List<Integer>> rooms) {
//        LinkedList<Integer> queue = new LinkedList<>();
//        queue.add(0);
//        boolean[] isVisited = new boolean[rooms.size()];
//        Arrays.fill(isVisited, false);
//        while (!queue.isEmpty()) {
//            Integer cur = queue.removeFirst();
//            isVisited[cur] = true;
//            List<Integer> curList = rooms.get(cur);
//            for (int x : curList) {
//                if (!isVisited[x]) queue.add(x);
//            }
//        }
//        for (boolean b : isVisited) {
//            if (!b) return false;
//        }
//        return true;
//    }
//
//    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
//        boolean[] isVisited = new boolean[rooms.size()];
//        Arrays.fill(isVisited, false);
//        dfs(isVisited, rooms, 0);
//        for (boolean b : isVisited) {
//            if (!b) return false;
//        }
//        return true;
//    }
//
//    public void dfs(boolean[] isVisited, List<List<Integer>> rooms, int index) {
//        isVisited[index] = true;
//        List<Integer> curList = rooms.get(index);
//        for (int x : curList) {
//            if (!isVisited[x]) {
//                dfs(isVisited, rooms, x);
//            }
//        }
//    }

    public boolean canVisitAllRooms1(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        dfs(visited, 0, rooms);
        for (boolean b : visited) {
            if (!b) return false;
        }
        return true;
    }

    public void dfs(boolean[] visited, int index, List<List<Integer>> rooms) {
        visited[index] = true;
        List<Integer> list = rooms.get(index);
        for (int x : list) {
            if (!visited[x]) {
                dfs(visited, x, rooms);
            }
        }
    }

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        LinkedList<Integer> queue = new LinkedList<>();
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        queue.add(0);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int cur = queue.removeFirst();
                visited[cur] = true;
                List<Integer> list = rooms.get(cur);
                for (int x : list) {
                    if (!visited[x]) queue.add(x);
                }
            }
        }
        for (boolean b : visited) if (!b) return false;
        return true;
    }
}
